package com.zsummer.test.ermian;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;

/**
 * @author zsummer
 * @since 2022/3/15
 */
public class Main {

    public static void main(String[] args) {
        //System.out.println(isYiWei("ad", "ad"));
        System.out.println(Arrays.asList(run("cbaebabacd", "abc")));
        System.out.println(Arrays.asList(run("abab", "ab")));
    }

    public static Integer[] run(String s, String p) {
        ArrayList<Integer> result = new ArrayList<>();
        int pLength = p.length();
        for (int i=0; i<s.length() - pLength + 1; i++) {
            if (isYiWei(s.substring(i,i + pLength), p)) {
                result.add(i);
            }
        }
        return result.toArray(new Integer[0]);
    }

    private static boolean isYiWei(String substring, String p) {
        LinkedList<Character> characters = new LinkedList<>();
        for (int i=0; i<substring.length(); i++) {
            characters.add(substring.charAt(i));
        }
        for (int i=0; i<p.length(); i++) {
            char c = p.charAt(i);
            //characters.removeIf(item -> item.equals(c));
            Iterator<Character> iterator = characters.iterator();
            while (iterator.hasNext()) {
                Character next = iterator.next();
                if (next.equals(c)) {
                    iterator.remove();
                    break;
                }
            }
        }
        return characters.size() == 0;
    }
}
